//class Solution {
//public:
//    void sortColors(vector<int>& nums) {
//        int left = -1, right = nums.size(), i = 0;
//        while (i < right)
//        {
//            if (nums[i] == 2)
//                swap(nums[i], nums[--right]);
//            else if (nums[i] == 1) i++;
//            else
//                swap(nums[i++], nums[++left]);
//        }
//        return;
//    }
//};




//class Solution {
//public:
//    vector<int> sortArray(vector<int>& nums) {
//        srand(time(nullptr));
//        Qsort(nums, 0, nums.size() - 1);
//        return nums;
//    }
//
//    void Qsort(vector<int>& nums, int l, int r)
//    {
//        if (l >= r) return;
//        int left = l - 1, right = r + 1, i = l;
//        int key = GetRandom(nums, l, r);
//        while (i < right)
//        {
//            if (nums[i] > key)
//                swap(nums[i], nums[--right]);
//            else if (nums[i] < key)
//                swap(nums[i++], nums[++left]);
//            else i++;
//        }
//        // [l, left] [left + 1, right - 1] [right, r]
//        Qsort(nums, l, left);
//        Qsort(nums, right, r);
//        return;
//    }
//
//    int GetRandom(vector<int>& nums, int left, int right)
//    {
//        int pos = left + rand() % (right - left + 1);
//        return nums[pos];
//    }
//};




//class Solution {
//public:
//    int GetRandom(vector<int>& nums, int left, int right)
//    {
//        int pos = left + rand() % (right - left + 1);
//        return nums[pos];
//    }
//    int findKthLargest(vector<int>& nums, int k) {
//        srand(time(nullptr));
//        return Qsort(nums, 0, nums.size() - 1, k);
//    }
//
//    int Qsort(vector<int>& nums, int l, int r, int k)
//    {
//        if (k == 0) return nums[l];
//        int i = l, left = l - 1, right = r + 1;
//        int key = GetRandom(nums, l, r);
//        while (i < right)
//        {
//            if (nums[i] > key)
//                swap(nums[i], nums[--right]);
//            else if (nums[i] < key)
//                swap(nums[i++], nums[++left]);
//            else i++;
//        }
//        // [l, left] [left + 1, right - 1] [right, r]
//        int a = r - right + 1, b = right - left - 1;
//        if (a >= k) return Qsort(nums, right, r, k);
//        else if (a + b >= k) return key;
//        else return Qsort(nums, l, left, k - a - b);
//    }
//};




//class Solution {
//public:
//    vector<int> smallestK(vector<int>& arr, int k) {
//        srand(time(nullptr));
//        Qsort(arr, 0, arr.size() - 1);
//
//        vector<int> ret;
//        ret.resize(k);
//        for (int i = 0; i < k; i++)
//            ret[i] = arr[i];
//        return ret;
//    }
//
//
//    void Qsort(vector<int>& arr, int l, int r)
//    {
//        if (l >= r) return;
//        int key = GetRandom(arr, l, r);
//        int i = l, left = l - 1, right = r + 1;
//        while (i < right)
//        {
//            if (arr[i] > key)
//                swap(arr[i], arr[--right]);
//            else if (arr[i] == key)
//                i++;
//            else
//                swap(arr[i++], arr[++left]);
//        }
//
//        Qsort(arr, l, left);
//        Qsort(arr, right, r);
//    }
//
//    int GetRandom(vector<int>& arr, int l, int r)
//    {
//        int pos = l + rand() % (r - l + 1);
//        return arr[pos];
//    }
//};

int PartSort(vector<int>& arr, int left, int right)
{
	int prev = left, cur = left + 1, keyi = left;
	while (cur <= right)
	{
		if (arr[cur] < arr[keyi] && ++prev != cur)
			swap(arr[cur], arr[prev]);
		cur++;
	}
	swap(arr[keyi], arr[prev]);
	keyi = prev;
	return keyi;
}

void Qsort(vector<int>& arr, int l, int r)
{
	if (l >= r) return;
	stack<std::make_pair<int, int>> st;
	st.push(std::make_pair(l, r));
	while (!st.empty())
	{
		auto top = st.top(); st.pop();
		if (top.first >= top.second) continue;
		int keyi = PartSort(arr, top.first, top.second);
		st.push(std::make_pair(l, keyi - 1));
		st.push(std::make_pair(keyi + 1, 1));;
	}
}